package solutions.leetcode.hard;

import com.google.gson.reflect.TypeToken;
import solutions.lib.BaseSolution;

import java.util.List;
import java.util.PriorityQueue;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/maximum-number-of-visible-points/">1610.可见点的最大数目</a>
 */
public class Solution1610 extends BaseSolution {

    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        if (angle == 360) {
            return points.size();
        }
        int px = location.get(0), py = location.get(1);

        PriorityQueue<Double> angleTemp = new PriorityQueue<>();
        int ps = 0;
        for (List<Integer> point : points) {
            int ox = point.get(0) - px;
            int oy = point.get(1) - py;
            if (ox == 0 && oy == 0) {
                ps++;
                continue;
            }
            angleTemp.offer(getAngle(oy, ox));
        }
        int len = angleTemp.size();
        double[] angles = new double[len * 2];
        for (int i = 0; i < len; i++) {
            angles[i] = angles[i + len] = angleTemp.poll();
        }

        int maxSum = 0;
        int left = 0, right = 1;
        while (right < angles.length) {
            while ((angles[right] - angles[left] + 360) % 360 > angle) {
                left++;
            }
            right++;
            if (right - left >= len) {
                return len + ps;
            }
            maxSum = Math.max(right - left, maxSum);
        }
        return maxSum + ps;
    }

    public double getAngle(int y, int x) {
        return Math.atan2(y, x) / Math.PI * 180 + 180;
    }

    public static void main(String[] args) {
//        Solution1610 solution = new Solution1610();
//        List<Integer> pos = parseString("[1,1]", new TypeToken<>() {
//        });
//        List<List<Integer>> points = parseString("[[1,0],[2,1]]", new TypeToken<>() {
//        });
//        System.out.println(solution.visiblePoints(points, 13, pos));
    }
}